package com.xb.Maximum_Binary_Tree_1470;

import org.junit.Test;

/**
 * 给定一个不重复的整数数组nums 。最大二叉树可以用下面的算法从nums 递归地构建:
 * <p>
 * 创建一个根节点，其值为nums 中的最大值。
 * 递归地在最大值左边的子数组前缀上构建左子树。
 * 递归地在最大值 右边 的子数组后缀上构建右子树。
 * 返回nums 构建的 最大二叉树 。
 * <p>
 * <p>
 * 输入：nums = [3,2,1,6,0,5]
 * 输出：[6,3,5,null,2,0,null,null,1]
 * 解释：递归调用如下所示：
 * - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 * - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 * - 空数组，无子节点。
 * - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 * - 空数组，无子节点。
 * - 只有一个元素，所以子节点是一个值为 1 的节点。
 * - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 * - 只有一个元素，所以子节点是一个值为 0 的节点。
 * - 空数组，无子节点。
 */
public class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        /*
         *找终止条件：当l>r时，说明数组中已经没元素了，自然当前返回的节点为null。
         每一级递归返回的信息是什么：返回的应该是当前已经构造好了最大二叉树的root节点。
         一次递归做了什么：找当前范围为[l,r]的数组中的最大值作为root节点，
          然后将数组划分成[l,bond-1]和[bond+1,r]两段，并分别构造成root的左右两棵子最大二叉树
         */
        return maxTree(nums, 0, nums.length - 1);
    }

    //生成最大二叉树的方法
    public TreeNode maxTree(int[] nums, int left, int right) {
        if (left > right || nums.length == 0) {
            return null;
        }
        int index= findMax(nums,left,right);
        TreeNode treeNode = new TreeNode(nums[index]);
        treeNode.left = maxTree(nums,left,index-1);
        treeNode.right = maxTree(nums,index+1,right);
        return treeNode;
    }

    //找出这个数组最大的值
    public int findMax(int[] nums, int left, int right) {
        int max = Integer.MIN_VALUE, maxIndex = 1;
        for (int i = left; i <= right; i++) {
            if (nums[i]>max){
                maxIndex = i;
                max = nums[i];
            }
        }
        return maxIndex;
    }
    @Test
    public void test(){
        int[] nums = {3,2,1,6,0,5};
        Solution solution = new Solution();
        TreeNode treeNode = solution.constructMaximumBinaryTree(nums);
        System.out.println(treeNode);
    }
}

//Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
